/*
2021-7-26
https://leetcode-cn.com/problems/maximum-compatibility-score-sum/
*/
class Solution {
public:

        int n,m,res;
        bool st[8]={false};
        vector<vector<int>> students,mentors;
        int cnt(int a,int b)
        {
            int res=0;
            for(int i=0;i<m;i++)
                res+=students[a][i] == mentors[b][i];
                    
            return res;
        }

        void dfs(int u,int sum)
        {
            if(u==n)
            {
                res=max(res,sum);
                return ;
            }
            
            for(int i=0;i<n;i++)
            {
                if(!st[i])
                {
                    st[i]=true;
                    dfs(u+1,sum+cnt(u,i));
                    st[i]=false;
                }
            }
            
        }

    int maxCompatibilitySum(vector<vector<int>>& _students, vector<vector<int>>& _mentors) {
        students = _students, mentors = _mentors;
        n=students.size();
        m=students[0].size();

        
        //res=0;
        dfs(0,0);
        return res;
    }
};
